The present invention relates to the field of encoding and decoding of digital data. More specifically, the present invention relates to methods and apparatus for efficient global motion compensation encoding and associated decoding of digital data.
Global motion compensation (GMC) is a powerful video compression technique. It uses one global parameter to describe the deformation of a current picture from a previous picture (usually caused by camera movement). However, GMC is commonly utilized together with traditional motion coding (MC) methods in compressing real world scenes where there are multiple objects each of which has its own motion. MPEG-4, as described in ISO/IEC 14496-2: 1999/FDAM 1: 2000(E) “Information Technology—Coding of audio-visual objects—Part 2: Visual, Amendment 1: Visual extensions”, N 3056 (December, 1999), adopts a similar compression routine. MPEG-4 includes GMC in the Advanced Simple Profile (ASP) (see, e.g., ISO/IEC 14496-2:1999/FDAM 4 “Information Technology—Coding of audio-visual objects—Part 2: Visual, Amendment 4: Streaming video profile” N 3094 (January 2001)).
GMC in MPEG-4 is similar to sprite coding in the sense that both operations calculate a warping parameter for every pixel in the frame based on a single Global Motion Vector (GMV). GMC, however, does not store the sprite piece in the global memory as is done in sprite coding, although the previous anchor frame can be considered a sprite piece in GMC. MPEG-4 allows sprite coding and GMC tools only in S-VOP (a picture that is coded using information obtained by warping whole or part of a static sprite) and up to eight components of the GMV can be transmitted in every S-VOP. As well known in the art, the acronym VOP refers to a “video object plane.” A discussion of sprite coding may be found in commonly assigned co-pending patent application Ser. No. 09/587,961 entitled “Global Motion Estimation for Sprite Coding” filed on Jun. 6, 2000.
A main drawback for GMC is its complexity, since for every pixel a warping parameter must be determined and warping must be performed based on a single GMV. “Warping” refers to a processing applied to extract a sprite VOP from a static sprite or a reference VOP. It consists of a global spatial transformation driven by a few motion parameters (0,2,4,6,8), to recover luminance, chrominance and shape information. The warping parameter calculations must be performed at a high precision (up to 1/16 pixel) to preserve accuracy.
Basic GMC Processing Routine
Operations in GMC encoding can be divided into five main tasks; i.e., estimation of GMV, calculation of matching cost, compensation in the luminance (luma) plane, compensation in the chrominance (chroma) plane and determination of the representative motion vector (MV). Only the last three processes are performed at the decoder. This section will provide a brief description of these processes to serve as a reference for the inventive algorithm described below. This section also describes the warping operation in detail, which is the most complex task among GMC operations.
Global Motion Estimation (GME) is computed before the main coding process (Macroblock (MB) loop). It is the most computationally intensive process in a GMC encoder (e.g., an MPEG-4 ASP encoder). GME determines the forward warping parameter (deforms the current VOP to match the original reference VOP) in the current VOP (which only occurs in sprite coding of an arbitrarily shaped object). GME in MPEG-4 adopts a hierarchical approach with each stage comprising up to 32 iterative steps. The Levenberg Marquadt algorithm, a nonlinear least square method, is used to adjust the warping parameter and minimize the matching error. More details on GME in MPEG-4 are provided in ISO/IEC 14496-2: 1999/FDAM 1: 2000(E) “Information Technology—Coding of audio-visual objects—Part 2 : Visual, Amendment 1: Visual extensions”, N 3056 (December, 1999) and in S. Fukunaga, Y. Nakaya, S. H. Son, T. Nagumo, “MPEG-4 Video Verification Model Version 15.0”, ISO/IEC JTC1/SC29/WG11 N3093 (December 1999).
Calculation of matching cost for mode decision is performed in the ME routine for every MB. Warped coefficients in the reconstructed reference VOP are selected for all coding pixels based on the warping parameter determined in GME. Similar to other ME methods in MPEG-4, SAD (sum of absolute difference) is adopted as a matching criteria in GMC. SAD from GMC with a proper bias is compared against the lowest SAD of the remaining MC modes and the mode (local or global) which gives the lowest overall SAD is chosen. Specification of the MPEG-4 mode decision can be found in S. Fukunaga, Y. Nakaya, S. H. Son, T. Nagumo, “MPEG-4 Video Verification Model Version 15.0”, ISO/IEC JTC1/SC29/WG11 N3093 (December 1999) and in the aforementioned co-pending patent application Ser. No. 09/587,961. Compensation in the luma plane is performed in the MC routine for every GMC selected MB. The encoder finds warped coefficients (which may not be the pixel at a full pel position) from the reconstructed reference VOP and stores them in the predicted MB. This predicted MB is subtracted from the coding MB to form a residual MB and the predicted MB together with the quantized residual MB forms the reconstructed current VOP. Compensation in the chroma plane also serves a similar purpose although the dimension of the warped parameter is reduced by half.
Determination of the representative MV can be done anywhere after the MC process and before the end of that MB coding routine. This process does not have any impact on the coding of the current MB. It is, however, necessary to have a representative MV so that the neighboring MB can use it as a predictor. This task basically calculates the MV of every pixel in the GMC selected MB and then finds an average from those MVs. This representative MV is quantized into either half or quarter pel accuracy following the accuracy of the local MV. The warping process is the key operation of all GMC tasks. Most GMC tasks require backward warping. However, GME calculates the warping parameter for an S-VOP using forward warping according to the following equations:
                              x          ′                =                ⁢                              ax            +            by            +            c                                gx            +            hy            +            1                                                            y          ′                =                ⁢                              dx            +            ey            +            f                                gx            +            hy            +            1                              where (x′, y′) is the coordinate in the previous anchor VOP, (x,y) is the coordinate in the current VOP and {a,b,c,d,e,f,g,h} are the components of the warping parameter (g and h are fixed to 1 for GMC).
The main concept of the backward warping process is to compute the location of the corresponding point in the reference VOP (applies inverse GMV) for every pixel in the GMC encoded MB. The warping process starts with reference point decoding which warps zero to three reference points (each corner of VOP) depending on the warping model employed. When the warping point is larger than one, the corresponding location of the reference point in the reference VOP includes both real and virtual components. Precision of both components is limited to 1/16 pel.
The next step in the warping process is to find a corresponding point for the starting pixel (top left position) of the GMC coded MB and to find spacing factors for horizontal and vertical directions. The warped reference points are used to compute the spacing factors, which specify the distance between the adjacent pixel after being warped. With the location of the corresponding starting pixel in the reference VOP, the location of other pixels is found by adding appropriate spacing factors. Precision of pixel location in the reference VOP is limited to 1/16 pixel.
As is clear from the above, the GMC processing routine is quite complex. In order to reduce the complexity, it would be advantageous to combine redundant processing functions in various GMC operations. It would be further advantageous to provide a single warping process for use in a variety of GMC operations (other than GME) in order to increase processing efficiency and speed. It would also be advantageous to provide such improvements without any quality degradation.
The methods and apparatus of the present invention provide the foregoing and other advantages.